package com.fallsvc.dayproblem.demo202511;

import java.util.Arrays;

/**
 * @auther falls_vc
 * description:
 * @date 2025/11/14  20:25
 */
public class Demo20251114 {
    public class ListNode {
     int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
  //https://leetcode.cn/problems/partition-list-lcci/
    // 分割链表
    public ListNode partition(ListNode head, int x) {
        if(head == null) return head;

        ListNode ret = head;
        ListNode prev = head;
        ListNode cur = head.next;
        while(cur != null) {
            // 头插
            if(cur.val < x) {
                prev.next = cur.next;
                cur.next = ret;
                ret = cur;

                cur = prev.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        return ret;
    }



      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;

          TreeNode() {
          }

          TreeNode(int val) {
              this.val = val;
          }

          TreeNode(int val, TreeNode left, TreeNode right) {
              this.val = val;
              this.left = left;
              this.right = right;
          }
      }
//https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/?envType=problem-list-v2&envId=divide-and-conquer
    // 将所有有序数组转化为平衡二叉树
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums == null || nums.length == 0) return null;

        return creatTree(nums,0,nums.length-1);
    }
    public TreeNode creatTree(int[] nums,int left,int right) {
        if(left > right) return null;

        int mid = (left + right) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = creatTree(nums,left,mid - 1);
        root.right = creatTree(nums,mid + 1,right);

        return root;
    }

    public static void main(String[] args) {
        int[] a = new int[]{1,2,3,4,5,6};
        System.arraycopy(new int[]{4,5,6,4,5,6,0,},0,a,0,6);
        System.out.println(Arrays.toString(a));
    }

    // https://leetcode.cn/problems/rotate-array/solutions/551039/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/?envType=study-plan-v2&envId=top-interview-150

    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }

    // 旋转k个数
    public void rotate2(int[] nums, int kk) {
        if(nums == null || nums.length == 0) return;

        int len = nums.length;
        int k = kk % len;

        reverse(nums,0,len-1-k);
        reverse(nums,len-k,len-1);
        reverse(nums,0,len-1);

    }
    public void reverse(int[] nums,int l,int r){
        while(l < r) {
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] =tmp;
            l++;
            r--;
        }
    }

}
